package crazy;

import java.util.Arrays;

class DataWrap1 implements Comparable<DataWrap1>
{
	int data;
	String flag;

	public DataWrap1(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}

	public String toString()
	{
		return data + flag;
	}

	public int compareTo(DataWrap1 dw)
	{
		return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);
	}
}

public class BucketSort
{
	public static void bucketSort(DataWrap1[] data, int min, int max)
	{
		int arrayLength = data.length;
		DataWrap1[] tmp = new DataWrap1[arrayLength];
		int[] buckets = new int[max - min];
		for (int i = 0; i < arrayLength; i++)
		{
			//第一轮遍历  落入各桶中的个数
			buckets[data[i].data - min]++;
			//System.out.println(Arrays.toString(buckets));
		}
		//System.out.println(Arrays.toString(buckets));
		for (int i = 1; i < max - min; i++)
		{
			//第二轮遍历  重新计算各个buckets数组的值
			buckets[i] = buckets[i] + buckets[i - 1];
		}
		//System.out.println(Arrays.toString(buckets));
		//System.out.println(Arrays.toString(tmp));
		System.arraycopy(data, 0, tmp, 0, arrayLength);
		//System.out.println(Arrays.toString(tmp));
		for (int k = arrayLength - 1; k >= 0; k--)
		{
			System.out.println("--"+buckets[(tmp[k].data - min)]);
			//以待排序最后一个元素3*为例， 找到新的buckets数组中元素3*对应桶的值，该值为5。这说明元素3*就应该排在第5位。
			//以待排序倒数第二个元素1为例，找到新的buckets数组中元素1对应桶的值，该值为3。说明元素1就应该排在第3位
			//以待排序倒数第四个元素3为例，找到新的buckets数组中元素3对应桶的值，该值为4。说明元素3就应该排在第4位
			//以待排序倒数第3个元素-3为例，找到新的buckets数组中元素-3对应桶的值，该值为1。说明元素-3就应该排在第1位
			//落入当前桶中的元素   在有序的序列应该排的位置   就是buckets数组中对应桶的值
			data[--buckets[tmp[k].data - min]] = tmp[k];
			System.out.println("   "+buckets[(tmp[k].data - min)]);
		}
		//
	}

	public static void main(String[] args)
	{
		DataWrap1[] data = { new DataWrap1(9, ""), new DataWrap1(5, ""),
				new DataWrap1(-1, ""), new DataWrap1(8, ""),
				new DataWrap1(5, "*"), new DataWrap1(7, ""),
				new DataWrap1(3, ""), new DataWrap1(-3, ""),
				new DataWrap1(1, ""), new DataWrap1(3, "*") };
		//System.out.println(java.util.Arrays.toString(data));
		bucketSort(data, -3, 10);
		//System.out.println(java.util.Arrays.toString(data));
	}
}